/*
15. 零钱兑换2
2022-10-26
link: https://leetcode.cn/problems/coin-change-ii/
question:
	给定不同面额的硬币数组coins和一个总金额amount。写出函数来计算可以凑成总金额的硬币组合数。
	假设每一种面额的硬币有无限个。
answer:
	一看到钱币数量不限，就知道是一个完全背包。
	注意：组合不强调元素之间的顺序，排列强调元素之间的顺序。
	动态规划五部曲：
	1、确定dp数组和下标含义：dp[j]凑成总金额j的货币组合数为dp[j]
	2、确定递推公式：
		dp[j]（考虑coins[i]的组合总和）就是所有的dp[j-coins[i]]（不考虑coins[i]）相加。
		dp[j] += dp[j - coins[i]];
	3、dp数组初始化：
	首先dp[0]一定要为1，dp[0]=1是递归公式的基础。
	从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
	下标非0的dp[j]初始化为0，这样累计加dp[j-coins[i]]的时候才不会影响真正的dp[j]。
	4、遍历顺序：
	外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），
	还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？
	如果外遍历物品，内遍历背包容量，得出dp[j]计算的是组合数。
	如果外遍历背包容量，内遍历物品，得出dp[j]计算的是排列数。
	本题要求凑成总和的组合数，元素之间要求没有顺序。所以选择先遍历物品。
	5、推到dp验证

总结：
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
*/
func change(amount int, coins []int) int {
	// dp数组创建和初始化
	dp := make([]int, amount+1)
	dp[0] = 1
	// 遍历
	for i := 0; i < len(coins); i++ { // 遍历物品
		for j := coins[i]; j <= amount; j++ { // 遍历背包
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}